{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Build a Matrix With Conditions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: buildMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给定条件下构造矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>正</strong>&nbsp;整数&nbsp;<code>k</code>&nbsp;，同时给你：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一个大小为 <code>n</code>&nbsp;的二维整数数组&nbsp;<code>rowConditions</code>&nbsp;，其中&nbsp;<code>rowConditions[i] = [above<sub>i</sub>, below<sub>i</sub>]</code>&nbsp;和</li>\n",
    "\t<li>一个大小为 <code>m</code>&nbsp;的二维整数数组&nbsp;<code>colConditions</code>&nbsp;，其中&nbsp;<code>colConditions[i] = [left<sub>i</sub>, right<sub>i</sub>]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>两个数组里的整数都是&nbsp;<code>1</code>&nbsp;到&nbsp;<code>k</code>&nbsp;之间的数字。</p>\n",
    "\n",
    "<p>你需要构造一个&nbsp;<code>k x k</code>&nbsp;的矩阵，<code>1</code>&nbsp;到&nbsp;<code>k</code>&nbsp;每个数字需要&nbsp;<strong>恰好出现一次</strong>&nbsp;。剩余的数字都是<b>&nbsp;</b><code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>矩阵还需要满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于所有 <code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;之间的下标&nbsp;<code>i</code>&nbsp;，数字&nbsp;<code>above<sub>i</sub></code>&nbsp;所在的 <strong>行</strong>&nbsp;必须在数字&nbsp;<code>below<sub>i</sub></code>&nbsp;所在行的上面。</li>\n",
    "\t<li>对于所有 <code>0</code>&nbsp;到 <code>m - 1</code>&nbsp;之间的下标&nbsp;<code>i</code>&nbsp;，数字&nbsp;<code>left<sub>i</sub></code>&nbsp;所在的 <b>列</b>&nbsp;必须在数字&nbsp;<code>right<sub>i</sub></code>&nbsp;所在列的左边。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回满足上述要求的 <strong>任意</strong>&nbsp;矩阵。如果不存在答案，返回一个空的矩阵。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/06/gridosdrawio.png\" style=\"width: 211px; height: 211px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]\n",
    "<b>输出：</b>[[3,0,0],[0,0,1],[0,2,0]]\n",
    "<b>解释：</b>上图为一个符合所有条件的矩阵。\n",
    "行要求如下：\n",
    "- 数字 1 在第 <strong>1</strong> 行，数字 2 在第 <strong>2</strong>&nbsp;行，1 在 2 的上面。\n",
    "- 数字 3 在第 <strong>0</strong>&nbsp;行，数字 2 在第 <strong>2</strong>&nbsp;行，3 在 2 的上面。\n",
    "列要求如下：\n",
    "- 数字 2 在第 <strong>1</strong>&nbsp;列，数字 1 在第 <strong>2</strong>&nbsp;列，2 在 1 的左边。\n",
    "- 数字 3 在第 <strong>0</strong>&nbsp;列，数字 2 在第 <strong>1</strong>&nbsp;列，3 在 2 的左边。\n",
    "注意，可能有多种正确的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]\n",
    "<b>输出：</b>[]\n",
    "<b>解释：</b>由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。\n",
    "没有符合条件的矩阵存在，所以我们返回空矩阵。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= k &lt;= 400</code></li>\n",
    "\t<li><code>1 &lt;= rowConditions.length, colConditions.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>rowConditions[i].length == colConditions[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= above<sub>i</sub>, below<sub>i</sub>, left<sub>i</sub>, right<sub>i</sub> &lt;= k</code></li>\n",
    "\t<li><code>above<sub>i</sub> != below<sub>i</sub></code></li>\n",
    "\t<li><code>left<sub>i</sub> != right<sub>i</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [build-a-matrix-with-conditions](https://leetcode.cn/problems/build-a-matrix-with-conditions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [build-a-matrix-with-conditions](https://leetcode.cn/problems/build-a-matrix-with-conditions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[1,2],[3,2]]\\n[[2,1],[3,2]]', '3\\n[[1,2],[2,3],[3,1],[2,3]]\\n[[2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from graphlib import TopologicalSorter\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def get_pos(cons: List[List[int]]) -> List[int]:\n",
    "            ts = TopologicalSorter()\n",
    "            for x in range(1, k + 1):\n",
    "                ts.add(x)\n",
    "            for x, y in cons:\n",
    "                ts.add(y, x)\n",
    "            pos = [0] * (k + 1)\n",
    "            for i, x in enumerate(ts.static_order()):\n",
    "                pos[x] = i\n",
    "            return pos\n",
    "\n",
    "        try:\n",
    "            book = {(i, j): x for x, (i, j) in enumerate(zip(get_pos(rowConditions), get_pos(colConditions)))}\n",
    "            return [[book.get((i, j), 0) for j in range(k)] for i in range(k)]\n",
    "        except:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        #这是一种拓扑排序\n",
    "        #定一个可以进行拓扑排序的函数\n",
    "        def topo_sort(edges):\n",
    "            g=[[] for _ in range(k)]\n",
    "            in_deg=[0]*k#每个节点的入度\n",
    "            for x,y in edges:\n",
    "                #g[x].append(y)表示x是y的先修节点  表示只有先学了x才可能学y\n",
    "                g[x-1].append(y-1)#是g[x].append(y)的变形  变化的都从0开始\n",
    "                in_deg[y-1]+=1#y对应的节点入度+1\n",
    "            order=[]#存放拓扑排序的数组\n",
    "            #因为是拓扑排序 首先可以先选择节点外面一圈没有入度的节点  因此这个比较符合广度优先\n",
    "            #广度优先使用双端队列(deque)\n",
    "            #先将所有入度为0的节点添加到双端队列中\n",
    "            q=deque(i for i,d in enumerate(in_deg) if d==0)\n",
    "            while q:\n",
    "                x=q.popleft()#这里的添加到拓扑序中的都是 从队列中弹出的元素\n",
    "                order.append(x)#添加到拓扑序列中\n",
    "                for y in g[x]:#将x所有的后续节点入度减一\n",
    "                    in_deg[y]-=1\n",
    "                    if in_deg[y]==0:\n",
    "                        q.append(y)#新节点入度为0  入双端队列\n",
    "            #如果长度不为所有结点的长度 那么表示存在环  不能将所有的节点添加到拓扑序中\n",
    "            return order if len(order)==k else None\n",
    "        \n",
    "        row=topo_sort(rowConditions)\n",
    "        if row is None:return []\n",
    "        col=topo_sort(colConditions)\n",
    "        if col is None:return []\n",
    "\n",
    "        #使用一个字典记录每个节点所在的列 pos[x]=j  表示节点x应该在第j列\n",
    "        pos={x:i for i,x in enumerate(col)}\n",
    "        ans=[[0]*k for _ in range(k)]\n",
    "        for i,x in enumerate(row):\n",
    "            ans[i][pos[x]]=x+1 #这里加一是因为前面都是将数据减一从0开始存储的\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        indeg = [0]*k\n",
    "        g = [[] for _ in range(k)]\n",
    "        q = deque([])\n",
    "        idx = 0\n",
    "        dicrow = [-1]*k\n",
    "        for above, below in rowConditions:\n",
    "            indeg[below-1] += 1\n",
    "            g[above-1].append(below-1)\n",
    "        for i in range(k):\n",
    "            if not indeg[i]:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            now = q.popleft()\n",
    "            dicrow[now] = idx\n",
    "            idx += 1\n",
    "            for nex in g[now]:\n",
    "                indeg[nex] -= 1\n",
    "                if not indeg[nex]:\n",
    "                    q.append(nex)\n",
    "        if idx != k:\n",
    "            return []\n",
    "        \n",
    "        indeg = [0]*k\n",
    "        g = [[] for _ in range(k)]\n",
    "        idx = 0\n",
    "        diccol = [-1]*k\n",
    "        for left, right in colConditions:\n",
    "            indeg[right-1] += 1\n",
    "            g[left-1].append(right-1)\n",
    "        for i in range(k):\n",
    "            if not indeg[i]:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            now = q.popleft()\n",
    "            diccol[now] = idx\n",
    "            idx += 1\n",
    "            for nex in g[now]:\n",
    "                indeg[nex] -= 1\n",
    "                if not indeg[nex]:\n",
    "                    q.append(nex)\n",
    "        if idx != k:\n",
    "            return []\n",
    "        res = [[0]*k for _ in range(k)]\n",
    "        for i in range(k):\n",
    "            res[dicrow[i]][diccol[i]] = i+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0]*k for _ in range(k)]\n",
    "        \n",
    "        g = [[]for i in range(k+1)]\n",
    "        d = [0]*(k+1)\n",
    "\n",
    "        def f(condition):\n",
    "            row = [0]*(k+1)\n",
    "            for x,y in condition:\n",
    "                g[x].append(y)\n",
    "                d[y]+=1\n",
    "            q = []\n",
    "            for i in range(1,k+1):\n",
    "                if d[i] == 0:\n",
    "                    q.append(i)\n",
    "            i = 0\n",
    "            while len(q):\n",
    "                x = q.pop(0)\n",
    "                row[x] = i\n",
    "                i+=1\n",
    "                for y in g[x]:\n",
    "                    d[y] -= 1\n",
    "                    if d[y] == 0:\n",
    "                        q.append(y)\n",
    "            for x in d:\n",
    "                if x:\n",
    "                    return []\n",
    "            return row\n",
    "        row = f(rowConditions)\n",
    "        g = [[]for i in range(k+1)]\n",
    "        d = [0]*(k+1)\n",
    "        col = f(colConditions)\n",
    "        if row ==[] or col == []:\n",
    "            return []\n",
    "        for i in range(1,k+1):\n",
    "            res[row[i]][col[i]] = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def topo_sort(s: List):\n",
    "            g = [[] * (k + 1) for _ in range(k + 1)]\n",
    "            ind = [0] * k\n",
    "            for a, b in s:\n",
    "                g[a].append(b)\n",
    "                ind[b - 1] += 1\n",
    "            order = []\n",
    "            q = deque([i + 1 for i, x in enumerate(ind) if x == 0])\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                order.append(x - 1)\n",
    "                for y in g[x]:\n",
    "                    ind[y - 1] -= 1\n",
    "                    if ind[y - 1] == 0:\n",
    "                        q.append(y)\n",
    "            return order if len(order) == k else None\n",
    "\n",
    "        rows = topo_sort(rowConditions)\n",
    "        if not rows: return []\n",
    "        cols = topo_sort(colConditions)\n",
    "        if not cols: return []\n",
    "\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        pos = {x:i for i, x in enumerate(cols)}\n",
    "\n",
    "        for i, x in enumerate(rows):\n",
    "            ans[i][pos[x]] = x + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        # 拓扑排序 + 构造\n",
    "        def topo_sort(edges: List[List[int]])-> List[int]:\n",
    "            g = [[] for _ in range(k)]\n",
    "            in_deg = [0] * k\n",
    "            for x, y in edges: \n",
    "                g[x - 1].append(y - 1)  # 顶点编号从0开始，方便计算\n",
    "                in_deg[y - 1] += 1\n",
    "\n",
    "            order = []\n",
    "            q = deque(i for i, d in enumerate(in_deg) if d == 0)\n",
    "            while q: # bfs\n",
    "                x = q.popleft()\n",
    "                order.append(x)\n",
    "                for y in g[x]:\n",
    "                    in_deg[y] -= 1\n",
    "                    if in_deg[y] == 0:\n",
    "                        q.append(y)\n",
    "            return order if len(order) == k else None\n",
    "\n",
    "        if (row := topo_sort(rowConditions)) is None or (col := topo_sort(colConditions)) is None:\n",
    "            return []\n",
    "        pos = {x: i for i, x in enumerate(col)}\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i, x in enumerate(row):\n",
    "            ans[i][pos[x]] = x + 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        def solve(arr: List[List[int]]) -> List[int]:\n",
    "            \n",
    "            inde=[0]*k\n",
    "            out=[[] for _ in range(k)]\n",
    "            for x,y in arr:\n",
    "                inde[y-1] +=1\n",
    "                out[x-1].append(y-1)\n",
    "            \n",
    "            q=deque(i for i,v in enumerate(inde) if v==0)\n",
    "            ans=[]\n",
    "            while q:\n",
    "                cur=q.popleft()\n",
    "                ans.append(cur)\n",
    "                for i in out[cur]:\n",
    "                    inde[i] -=1\n",
    "                    if inde[i]==0:\n",
    "                        q.append(i)\n",
    "\n",
    "            return ans if len(ans)==k else None\n",
    "\n",
    "        # def solve(edges: List[List[int]]) -> List[int]:\n",
    "        #     g = [[] for _ in range(k)]\n",
    "        #     in_deg = [0] * k\n",
    "        #     for x, y in edges:\n",
    "        #         g[x - 1].append(y - 1)  # 顶点编号从 0 开始，方便计算\n",
    "        #         in_deg[y - 1] += 1\n",
    "        #     order = []\n",
    "        #     q = deque(i for i, d in enumerate(in_deg) if d == 0)\n",
    "        #     while q:\n",
    "        #         x = q.popleft()\n",
    "        #         order.append(x)\n",
    "        #         for y in g[x]:\n",
    "        #             in_deg[y] -= 1\n",
    "        #             if in_deg[y] == 0:\n",
    "        #                 q.append(y)\n",
    "        #     return order if len(order) == k else None\n",
    "\n",
    "\n",
    "        row=solve(rowConditions)\n",
    "        if row is None: return []\n",
    "        #print(row)\n",
    "        col=solve(colConditions)\n",
    "        if col is None: return []\n",
    "        #print(col)\n",
    "        pos={x:i for i,x in enumerate(col)}\n",
    "        res=[[0]*k for _ in range(k)]\n",
    "        for i,x in enumerate(row):\n",
    "            res[i][pos[x]]=x+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def topo_sort(edges: List[List[int]]) -> List[int]:\n",
    "            g = [[] for _ in range(k)]\n",
    "            in_deg = [0] * k\n",
    "            for x, y in edges:\n",
    "                g[x - 1].append(y - 1)  # 顶点编号从 0 开始，方便计算\n",
    "                in_deg[y - 1] += 1\n",
    "            order = []\n",
    "            q = deque(i for i, d in enumerate(in_deg) if d == 0)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                order.append(x)\n",
    "                for y in g[x]:\n",
    "                    in_deg[y] -= 1\n",
    "                    if in_deg[y] == 0:\n",
    "                        q.append(y)\n",
    "            return order if len(order) == k else None\n",
    "\n",
    "        if (row := topo_sort(rowConditions)) is None or (col := topo_sort(colConditions)) is None:\n",
    "            return []\n",
    "        pos = {x: i for i, x in enumerate(col)}\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i, x in enumerate(row):\n",
    "            ans[i][pos[x]] = x + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        # def solve(arr):\n",
    "        #     ans=[]\n",
    "        #     inde=[0]*k\n",
    "        #     out=[[] for _ in range(k)]\n",
    "        #     for x,y in arr:\n",
    "        #         inde[x-1] +=1\n",
    "        #         out[y-1].append(x-1)\n",
    "            \n",
    "        #     q=deque(i for i,v in enumerate(inde) if v==0)\n",
    "            \n",
    "        #     while q:\n",
    "        #         cur=q.popleft()\n",
    "        #         ans.append(cur)\n",
    "        #         for i in out[cur]:\n",
    "        #             inde[i] -=1\n",
    "        #             if inde[i]==0:\n",
    "        #                 q.append(i)\n",
    "\n",
    "        #     return ans if len(ans)==k else None\n",
    "\n",
    "        def solve(edges: List[List[int]]) -> List[int]:\n",
    "            g = [[] for _ in range(k)]\n",
    "            in_deg = [0] * k\n",
    "            for x, y in edges:\n",
    "                g[x - 1].append(y - 1)  # 顶点编号从 0 开始，方便计算\n",
    "                in_deg[y - 1] += 1\n",
    "            order = []\n",
    "            q = deque(i for i, d in enumerate(in_deg) if d == 0)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                order.append(x)\n",
    "                for y in g[x]:\n",
    "                    in_deg[y] -= 1\n",
    "                    if in_deg[y] == 0:\n",
    "                        q.append(y)\n",
    "            return order if len(order) == k else None\n",
    "\n",
    "\n",
    "        row=solve(rowConditions)\n",
    "        if row is None: return []\n",
    "        #print(row)\n",
    "        col=solve(colConditions)\n",
    "        if col is None: return []\n",
    "        #print(col)\n",
    "        pos={x:i for i,x in enumerate(col)}\n",
    "        res=[[0]*k for _ in range(k)]\n",
    "        for i,x in enumerate(row):\n",
    "            res[i][pos[x]]=x+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def go(conditions):\n",
    "            deg = [0] * (k + 1)\n",
    "            g = defaultdict(list)\n",
    "            seq = [0] * (k + 1)\n",
    "            for a, b in conditions:\n",
    "                deg[b] += 1\n",
    "                g[a].append(b)\n",
    "            q = []\n",
    "            now = 0\n",
    "            for i in range(1, k + 1):\n",
    "                if deg[i] == 0:\n",
    "                    q.append(i)\n",
    "                    seq[i] = now\n",
    "                    now += 1\n",
    "            while q:\n",
    "                node = q.pop()\n",
    "                for son in g[node]:\n",
    "                    deg[son] -= 1\n",
    "                    if deg[son] == 0:\n",
    "                        q.append(son)\n",
    "                        seq[son] = now\n",
    "                        now += 1\n",
    "            return [] if now != k else seq\n",
    "        \n",
    "        row = go(rowConditions)\n",
    "        if not row:\n",
    "            return []\n",
    "        col = go(colConditions)\n",
    "        if not col:\n",
    "            return []\n",
    "        ret = [[0] * k for _ in range(k)]\n",
    "        for i in range(1, k + 1):\n",
    "            ret[row[i]][col[i]] = i\n",
    "        return ret\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0]*k for _ in range(k)]\n",
    "        \n",
    "        def f(g,d,condition):\n",
    "            row = [0]*(k+1)\n",
    "            for x,y in condition:\n",
    "                g[x].append(y)\n",
    "                d[y]+=1\n",
    "            q = [i for i in range(1,k+1) if d[i]==0 ]\n",
    "            i = 0\n",
    "            while len(q):\n",
    "                x = q.pop(0)\n",
    "                row[x] = i\n",
    "                i+=1\n",
    "                for y in g[x]:\n",
    "                    d[y] -= 1\n",
    "                    if d[y] == 0:\n",
    "                        q.append(y)\n",
    "            return row if i==k else []\n",
    "            \n",
    "        row = f([[]for i in range(k+1)], [0]*(k+1), rowConditions)\n",
    "        col = f([[]for i in range(k+1)], [0]*(k+1), colConditions)\n",
    "        if row ==[] or col == []:\n",
    "            return []\n",
    "        for i in range(1,k+1):\n",
    "            res[row[i]][col[i]] = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def topSort(links):\n",
    "            inDegrees = [0]*(k+1)\n",
    "            edges = [[] for _ in range(k+1)]\n",
    "            for a, b in links:\n",
    "                inDegrees[b] += 1\n",
    "                edges[a].append(b)\n",
    "            q = deque(x for x in range(1, k+1) if not inDegrees[x])\n",
    "            res = []\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                res.append(x)\n",
    "                for y in edges[x]:\n",
    "                    inDegrees[y] -= 1\n",
    "                    if not inDegrees[y]:\n",
    "                        q.append(y)\n",
    "            return res \n",
    "        rowSeq = topSort(rowConditions)\n",
    "        if len(rowSeq) != k: return []\n",
    "        colSeq = topSort(colConditions)\n",
    "        if len(colSeq) != k: return []\n",
    "        rowOffs = [0]*(k+1)\n",
    "        for r, x in enumerate(rowSeq):\n",
    "            rowOffs[x] = r\n",
    "        res = [[0]*k for _ in range(k)]\n",
    "        for c, x in enumerate(colSeq):\n",
    "            r = rowOffs[x]\n",
    "            res[r][c] = x\n",
    "        return res\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def topoSort(nums: List[List[int]]) -> List[int]:\n",
    "            nexts = [[] for _ in range(k)]\n",
    "            preCnts = [0] * k\n",
    "            for a, b in nums:\n",
    "                nexts[a - 1].append(b - 1)\n",
    "                preCnts[b - 1] += 1\n",
    "            que = deque(i for i in range(k) if preCnts[i] == 0)\n",
    "            ordered = []\n",
    "            while len(que):\n",
    "                cur = que.popleft()\n",
    "                ordered.append(cur)\n",
    "                for n in nexts[cur]:\n",
    "                    preCnts[n] -= 1\n",
    "                    if not preCnts[n]:\n",
    "                        que.append(n)\n",
    "            return ordered if len(ordered) == k else None\n",
    "        \n",
    "        orderedRow, orderedCol = topoSort(rowConditions), topoSort(colConditions)\n",
    "        if not orderedRow or not orderedCol:\n",
    "            return []\n",
    "        colOrder = {num: pos for pos, num in enumerate(orderedCol)}\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for row, num in enumerate(orderedRow):\n",
    "            ans[row][colOrder[num]] = num + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def topo_sort(edges: List[List[int]]) -> List[int]:\n",
    "            g = [[] for _ in range(k)]\n",
    "            in_deg = [0] * k\n",
    "            for x, y in edges:\n",
    "                g[x - 1].append(y - 1)  # 顶点编号从 0 开始，方便计算\n",
    "                in_deg[y - 1] += 1\n",
    "            order = []\n",
    "            q = deque(i for i, d in enumerate(in_deg) if d == 0)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                order.append(x)\n",
    "                for y in g[x]:\n",
    "                    in_deg[y] -= 1\n",
    "                    if in_deg[y] == 0:\n",
    "                        q.append(y)\n",
    "            return order if len(order) == k else None\n",
    "\n",
    "        if (row := topo_sort(rowConditions)) is None or (col := topo_sort(colConditions)) is None:\n",
    "            return []\n",
    "        pos = {x: i for i, x in enumerate(col)}\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i, x in enumerate(row):\n",
    "            ans[i][pos[x]] = x + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def topo_sort(edges: List[List[int]]) -> List[int]:\n",
    "            g = [[] for _ in range(k)]\n",
    "            in_deg = [0] * k\n",
    "            for x, y in edges:\n",
    "                g[x - 1].append(y - 1)  # 顶点编号从 0 开始，方便计算\n",
    "                in_deg[y - 1] += 1\n",
    "            order = []\n",
    "            q = deque(i for i, d in enumerate(in_deg) if d == 0)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                order.append(x)\n",
    "                for y in g[x]:\n",
    "                    in_deg[y] -= 1\n",
    "                    if in_deg[y] == 0:\n",
    "                        q.append(y)\n",
    "            return order if len(order) == k else None\n",
    "\n",
    "        if (row := topo_sort(rowConditions)) is None or (col := topo_sort(colConditions)) is None:\n",
    "            return []\n",
    "        pos = {x: i for i, x in enumerate(col)}\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i, x in enumerate(row):\n",
    "            ans[i][pos[x]] = x + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def topo_sort(edges: List[List[int]]) -> List[int]:\n",
    "            g = [[] for _ in range(k)]\n",
    "            in_deg = [0] * k\n",
    "            for x, y in edges:\n",
    "                g[x - 1].append(y - 1)  # 顶点编号从 0 开始，方便计算\n",
    "                in_deg[y - 1] += 1\n",
    "            order = []\n",
    "            q = deque(i for i, d in enumerate(in_deg) if d == 0)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                order.append(x)\n",
    "                for y in g[x]:\n",
    "                    in_deg[y] -= 1\n",
    "                    if in_deg[y] == 0:\n",
    "                        q.append(y)\n",
    "            return order if len(order) == k else None\n",
    "\n",
    "        if (row := topo_sort(rowConditions)) is None or (col := topo_sort(colConditions)) is None:\n",
    "            return []\n",
    "        pos = {x: i for i, x in enumerate(col)}\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i, x in enumerate(row):\n",
    "            ans[i][pos[x]] = x + 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def topo_sort(nums: List[List[int]]) -> List[int]:\n",
    "            g, deg = [[] for _ in range(k)], [0] * k\n",
    "            for a, b in nums:\n",
    "                a -= 1\n",
    "                b -= 1\n",
    "                g[a].append(b)\n",
    "                deg[b] += 1\n",
    "            q, res = deque([i for i, v in enumerate(deg) if v == 0]), []\n",
    "            while q:\n",
    "                res.append(q.popleft())\n",
    "                for b in g[res[-1]]:\n",
    "                    deg[b] -= 1\n",
    "                    if deg[b] == 0:\n",
    "                        q.append(b)\n",
    "            if any(x != 0 for x in deg): return []\n",
    "            return res\n",
    "        \n",
    "        row, col = topo_sort(rowConditions), topo_sort(colConditions)\n",
    "        if not row or not col: return []\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        idx = {}\n",
    "        for i, v in enumerate(col):\n",
    "            idx[v] = i\n",
    "        for i, v in enumerate(row):\n",
    "            ans[i][idx[v]] = v + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @ staticmethod\n",
    "    def genSeq(k, conditions):\n",
    "        neighbors = [[] for _ in range(k)]\n",
    "        degs = [0] * k\n",
    "        for condition in conditions:\n",
    "            neighbors[condition[0] - 1].append(condition[1] - 1)\n",
    "            degs[condition[1] - 1] += 1\n",
    "        ans = []\n",
    "        q = deque()\n",
    "        for i in range(k):\n",
    "            if degs[i] == 0: q.append(i)\n",
    "        while len(q) > 0:\n",
    "            i = q.popleft()\n",
    "            ans.append(i)\n",
    "            for j in neighbors[i]: \n",
    "                degs[j] -= 1\n",
    "                if degs[j] == 0: q.append(j)\n",
    "        return ans\n",
    "\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        row, col = Solution.genSeq(k, rowConditions), Solution.genSeq(k, colConditions)\n",
    "        if len(row) < k or len(col) < k: return []\n",
    "        dr, dc = {row[i]:i for i in range(k)}, {col[i]:i for i in range(k)}\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i in range(k):\n",
    "            ans[dr[i]][dc[i]] = i + 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def topo_layers(num, arr : List[List[int]]): # 直接返回分层，如果有环，就返回空 []\n",
    "            adjecency = [[] for _ in range(num + 1)]\n",
    "            indegrees = [0] * (num + 1)\n",
    "            for start, to in arr:\n",
    "                if to in adjecency[start]:\n",
    "                    continue\n",
    "                adjecency[start].append(to)\n",
    "                indegrees[to] += 1\n",
    "            layer = deque([])\n",
    "            for i in range(1, len(indegrees)):\n",
    "                if indegrees[i] == 0:\n",
    "                    layer.append(i)\n",
    "            layers = []\n",
    "            visited_count = 0\n",
    "            while layer:\n",
    "                count = len(layer)\n",
    "                visited_count += count\n",
    "                layers.append(list(layer))\n",
    "                for _ in range(count):\n",
    "                    curr = layer.popleft()\n",
    "                    for i in adjecency[curr]:\n",
    "                        indegrees[i] -= 1\n",
    "                        if indegrees[i] == 0:\n",
    "                            layer.append(i)\n",
    "            return layers if visited_count == num else []\n",
    "        rowLayers = topo_layers(k, rowConditions)\n",
    "        colLayers = topo_layers(k, colConditions)\n",
    "        if len(rowLayers) == 0 or len(colLayers) == 0:\n",
    "            return []\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        locations = [[] for _ in range(k + 1)]\n",
    "        for row in range(len(rowLayers)):\n",
    "            for element in rowLayers[row]:\n",
    "                locations[element].append(row)\n",
    "        curr_col = 0\n",
    "        for col in range(len(colLayers)):\n",
    "            for element in colLayers[col]:\n",
    "                locations[element].append(curr_col)\n",
    "                curr_col += 1\n",
    "        for i in range(1, len(locations)):\n",
    "            ans[locations[i][0]][locations[i][1]] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        idxr = defaultdict(int)\n",
    "        idxc = defaultdict(int)\n",
    "\n",
    "        gr = [[] for _ in range(k+1)]\n",
    "        degr = [0] * (k+1)\n",
    "        gc = [[] for _ in range(k+1)]\n",
    "        degc = [0] * (k+1)\n",
    "\n",
    "        for x, y in rowConditions:\n",
    "            degr[y] += 1\n",
    "            gr[x].append(y)\n",
    "\n",
    "        for x, y in colConditions:\n",
    "            degc[y] += 1\n",
    "            gc[x].append(y)\n",
    "\n",
    "        def top_sort(g, deg, tp):\n",
    "            q = deque([i for i in range(1, k+1) if not deg[i]])\n",
    "            tot = set()\n",
    "            idx = 0\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                tot.add(cur)\n",
    "                if tp:\n",
    "                    idxr[cur] = idx\n",
    "                else:\n",
    "                    idxc[cur] = idx\n",
    "                idx += 1\n",
    "                for nxt in g[cur]:\n",
    "                    deg[nxt] -= 1\n",
    "                    if not deg[nxt]:\n",
    "                        q.append(nxt)\n",
    "            return len(tot) == k\n",
    "\n",
    "        if top_sort(gr, degr, 1) and top_sort(gc, degc, 0):\n",
    "            for i in range(1, k+1):\n",
    "                ans[idxr[i]][idxc[i]] = i\n",
    "            return ans\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def get(v:List[List[int]]) -> List[int]:\n",
    "            deg = [0] * (k + 1)\n",
    "            g = [[] for _ in range(k + 1)]\n",
    "            ans = [0] * k\n",
    "            for i, j in v:\n",
    "                g[i].append(j)\n",
    "                deg[j] += 1\n",
    "            q = deque(i for i in range(1, k + 1) if deg[i] == 0)\n",
    "            idx = 0 # 记录第几个位置出现\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                ans[cur - 1] = idx\n",
    "                idx += 1\n",
    "                for nxt in g[cur]:\n",
    "                    deg[nxt] -= 1\n",
    "                    if deg[nxt] == 0:\n",
    "                        q.append(nxt)\n",
    "            if idx != k:\n",
    "                return []\n",
    "            return ans\n",
    "        row = get(rowConditions)\n",
    "        col = get(colConditions)\n",
    "        if len(row) != k or len(col) != k:\n",
    "            return []\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i in range(k):\n",
    "            ans[row[i]][col[i]] = i + 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        rg = collections.defaultdict(list)\n",
    "        rInd = collections.Counter()\n",
    "        cg = collections.defaultdict(list)\n",
    "        cInd = collections.Counter()\n",
    "        for a, b in rowConditions:\n",
    "            rg[a - 1].append(b - 1)\n",
    "            rInd[b - 1] += 1 \n",
    "        for l, r in colConditions:\n",
    "            cg[l - 1].append(r - 1)\n",
    "            cInd[r - 1] += 1 \n",
    "        res = [[0 for _ in range(k)] for _ in range(k)]\n",
    "        rows = [0] * k\n",
    "        cols = [0] * k \n",
    "        def build(g, ind, res):\n",
    "            start = 0\n",
    "            cnt = 0\n",
    "            queue = collections.deque([i for i in range(k) if ind[i] == 0])\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                res[cur] = start\n",
    "                start += 1 \n",
    "                cnt += 1 \n",
    "                for nei in g[cur]:\n",
    "                    ind[nei] -= 1 \n",
    "                    if ind[nei] == 0:\n",
    "                        queue.append(nei)\n",
    "            return cnt == k\n",
    "        if not build(rg, rInd, rows):\n",
    "            return []\n",
    "        if not build(cg, cInd, cols):\n",
    "            return []\n",
    "        for i in range(k):\n",
    "            res[rows[i]][cols[i]] = i + 1 \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def topoSort(n: int, adjList: List[List[int]], directed=True) -> Tuple[List[int], bool]:\n",
    "    \"\"\"求图的拓扑排序.\"\"\"\n",
    "    if directed:\n",
    "        deg = [0] * n\n",
    "        for i in range(n):\n",
    "            for j in adjList[i]:\n",
    "                deg[j] += 1\n",
    "    else:\n",
    "        deg = [len(adj) for adj in adjList]\n",
    "\n",
    "    startDeg = 0 if directed else 1\n",
    "    queue = deque([v for v in range(n) if deg[v] == startDeg])\n",
    "    res = []\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        res.append(cur)\n",
    "        for next in adjList[cur]:\n",
    "            deg[next] -= 1\n",
    "            if deg[next] == startDeg:\n",
    "                queue.append(next)\n",
    "\n",
    "    if len(res) != n:\n",
    "        return [], False\n",
    "    return res, True\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(\n",
    "        self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]\n",
    "    ) -> List[List[int]]:\n",
    "        adjList1 = [[] for _ in range((k))]\n",
    "        for pre, cur in rowConditions:\n",
    "            pre, cur = pre - 1, cur - 1\n",
    "            adjList1[pre].append(cur)\n",
    "        rowOrder, ok = topoSort(k, adjList1)\n",
    "        if not ok:\n",
    "            return []\n",
    "\n",
    "        adjList2 = [[] for _ in range((k))]\n",
    "        for pre, cur in colConditions:\n",
    "            pre, cur = pre - 1, cur - 1\n",
    "            adjList2[pre].append(cur)\n",
    "        colOrder, ok = topoSort(k, adjList2)\n",
    "        if not ok:\n",
    "            return []\n",
    "\n",
    "        mp1 = {num: r for r, num in enumerate(rowOrder)}\n",
    "        mp2 = {num: c for c, num in enumerate(colOrder)}\n",
    "        res = [[0] * k for _ in range(k)]\n",
    "        for num in range(k):\n",
    "            res[mp1[num]][mp2[num]] = num + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        rows,cols=collections.defaultdict(list),collections.defaultdict(list)\n",
    "        rneeds,cneeds=[0]*k,[0]*k\n",
    "        for a,b in rowConditions:\n",
    "            rows[a-1].append(b-1)\n",
    "            rneeds[b-1]+=1\n",
    "        for l,r in colConditions :\n",
    "            cols[l-1].append(r-1)\n",
    "            cneeds[r-1]+=1\n",
    "        def top_sort(needs,arr):\n",
    "            ans=[]\n",
    "            q=deque(i for i,n in enumerate(needs) if n==0)\n",
    "            while q:\n",
    "                l = q.popleft()\n",
    "                ans.append(l)\n",
    "                for low in arr[l]:\n",
    "                    needs[low]-=1\n",
    "                    if needs[low]==0:\n",
    "                        q.append(low)\n",
    "            return ans\n",
    "        rq=top_sort(rneeds, rows)\n",
    "        if len(rq)!=k:return []\n",
    "        cq=top_sort(cneeds, cols)  \n",
    "        if len(cq)!=k:return []\n",
    "        pos={e:i for i,e in enumerate(cq)}\n",
    "        res=[[0]*k for _ in range(k)]\n",
    "        for i,x in enumerate(rq):\n",
    "            res[i][pos[x]]=x+1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def helper(conditions):\n",
    "            # topological sort\n",
    "            graph = collections.defaultdict(list)\n",
    "            indgrees = [0]*(1+k)\n",
    "            for a,b in conditions:\n",
    "                graph[a].append(b)\n",
    "                indgrees[b]+=1\n",
    "            pos = 0\n",
    "            q = [i for i in range(1,k+1) if indgrees[i]==0]\n",
    "            res = [0]*(1+k)\n",
    "            while q:\n",
    "                node = q.pop()\n",
    "                res[node] = pos\n",
    "                pos += 1\n",
    "                for nei in graph[node]:\n",
    "                    indgrees[nei] -= 1\n",
    "                    if indgrees[nei] == 0:\n",
    "                        q.append(nei)\n",
    "            return res if pos == k else []\n",
    "        \n",
    "        rows = helper(rowConditions)\n",
    "        cols = helper(colConditions)\n",
    "\n",
    "        if rows and cols:\n",
    "            res = [[0]*k for _ in range(k)]\n",
    "            for i in range(1,k+1):\n",
    "                res[rows[i]][cols[i]] = i\n",
    "            return res\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def topo_topk(edges):\n",
    "            # 建立先后关系图\n",
    "            g = [[] for _ in range(k)]\n",
    "            left = [0] * k # 记录第i门课程剩余先修课的数目，如果为0，代表可以修第i门课\n",
    "            for x,y in edges:\n",
    "                g[x-1].append(y-1)\n",
    "                left[y-1] += 1\n",
    "            order = [] # 拓扑序\n",
    "            q = deque([i for i,x in enumerate(left) if x == 0])\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                order.append(x)\n",
    "                for y in g[x]:\n",
    "                    left[y] -= 1  # x指向的课程，它的先修课-1\n",
    "                    if left[y] == 0:  # 学完了所有的先修课\n",
    "                        q.append(y)\n",
    "            # 如果拓扑序的节点数和所有的节点数不像等证明存在环，没有办法进行拓扑排序\n",
    "            return order if len(order) == k else None  \n",
    "        row = topo_topk(rowConditions)\n",
    "        if row is None:\n",
    "            return []\n",
    "        col = topo_topk(colConditions)\n",
    "        if col is None:\n",
    "            return []\n",
    "        print(row)\n",
    "        print(col)\n",
    "        ans = [[0 for _ in range(k)] for _ in range(k)]\n",
    "        # 每个元素在第几列\n",
    "        pos = {x:i for i,x in enumerate(col)}\n",
    "        for i,x in enumerate(row):\n",
    "            ans[i][pos[x]] = x+1\n",
    "        return ans \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        indeg_row = [0] * k\n",
    "        indeg_col = [0] * k\n",
    "        row = defaultdict(list)\n",
    "        col = defaultdict(list)\n",
    "        for x, y in rowConditions:\n",
    "            row[x - 1].append(y - 1)\n",
    "            indeg_row[y - 1] += 1\n",
    "        for x, y in colConditions:\n",
    "            col[x - 1].append(y - 1)\n",
    "            indeg_col[y - 1] += 1\n",
    "        q1 = deque(i for i, x in enumerate(indeg_row) if x == 0)\n",
    "        q2 = deque(i for i, x in enumerate(indeg_col) if x == 0)\n",
    "        a1 = []\n",
    "        a2 = []\n",
    "        while q1:\n",
    "            i = q1.popleft()\n",
    "            a1.append(i + 1)\n",
    "            for j in row[i]:\n",
    "                indeg_row[j] -= 1\n",
    "                if indeg_row[j] == 0:\n",
    "                    q1.append(j)\n",
    "        while q2:\n",
    "            i = q2.popleft()\n",
    "            a2.append(i + 1)\n",
    "            for j in col[i]:\n",
    "                indeg_col[j] -= 1\n",
    "                if indeg_col[j] == 0:\n",
    "                    q2.append(j)\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i, x in enumerate(a1):\n",
    "            for j, y in enumerate(a2):\n",
    "               if x == y:\n",
    "                   ans[i][j] = x \n",
    "        return ans if len(a1) == len(a2) == k else []\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def go(conditions):\n",
    "            deg = [0] * (k + 1)\n",
    "            g = [[] for _ in range(k + 1)]\n",
    "            seq = [0] * (k + 1)\n",
    "            for a, b in conditions:\n",
    "                deg[b] += 1\n",
    "                g[a].append(b)\n",
    "            q = []\n",
    "            now = 0\n",
    "            for i in range(1, k + 1):\n",
    "                if deg[i] == 0:\n",
    "                    q.append(i)\n",
    "                    seq[i] = now\n",
    "                    now += 1\n",
    "            while q:\n",
    "                node = q.pop()\n",
    "                for son in g[node]:\n",
    "                    deg[son] -= 1\n",
    "                    if deg[son] == 0:\n",
    "                        q.append(son)\n",
    "                        seq[son] = now\n",
    "                        now += 1\n",
    "            return [] if now != k else seq\n",
    "        \n",
    "        row = go(rowConditions)\n",
    "        if not row:\n",
    "            return []\n",
    "        col = go(colConditions)\n",
    "        if not col:\n",
    "            return []\n",
    "        ret = [[0] * k for _ in range(k)]\n",
    "        for i in range(1, k + 1):\n",
    "            ret[row[i]][col[i]] = i\n",
    "        return ret\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        rg = collections.defaultdict(list)\n",
    "        cg = collections.defaultdict(list)\n",
    "        rInd = collections.Counter()\n",
    "        cInd = collections.Counter()\n",
    "        rows = [0] * k \n",
    "        cols = [0] * k \n",
    "        for a, b in rowConditions:\n",
    "            rg[a - 1].append(b - 1)\n",
    "            rInd[b - 1] += 1 \n",
    "        for a, b in colConditions:\n",
    "            cg[a - 1].append(b - 1)\n",
    "            cInd[b - 1] += 1 \n",
    "        def build(g, ind, res):\n",
    "            start = 0\n",
    "            cnt = 0\n",
    "            queue = collections.deque([i for i in range(k) if ind[i] == 0])\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                res[cur] = start\n",
    "                start += 1 \n",
    "                cnt += 1 \n",
    "                for nei in g[cur]:\n",
    "                    ind[nei] -= 1 \n",
    "                    if ind[nei] == 0:\n",
    "                        queue.append(nei)\n",
    "            return cnt == k \n",
    "        if not build(rg, rInd, rows) or not build(cg, cInd, cols):\n",
    "            return []\n",
    "        res = [[0 for _ in range(k)] for _ in range(k)]\n",
    "        for i in range(k):\n",
    "            res[rows[i]][cols[i]] = i + 1 \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        indeg_row = [0] * k\n",
    "        indeg_col = [0] * k\n",
    "        row = defaultdict(list)\n",
    "        col = defaultdict(list)\n",
    "        for x, y in rowConditions:\n",
    "            row[x - 1].append(y - 1)\n",
    "            indeg_row[y - 1] += 1\n",
    "        for x, y in colConditions:\n",
    "            col[x - 1].append(y - 1)\n",
    "            indeg_col[y - 1] += 1\n",
    "        q1 = deque(i for i, x in enumerate(indeg_row) if x == 0)\n",
    "        q2 = deque(i for i, x in enumerate(indeg_col) if x == 0)\n",
    "        a1 = []\n",
    "        a2 = []\n",
    "        while q1:\n",
    "            i = q1.popleft()\n",
    "            a1.append(i + 1)\n",
    "            for j in row[i]:\n",
    "                indeg_row[j] -= 1\n",
    "                if indeg_row[j] == 0:\n",
    "                    q1.append(j)\n",
    "        while q2:\n",
    "            i = q2.popleft()\n",
    "            a2.append(i + 1)\n",
    "            for j in col[i]:\n",
    "                indeg_col[j] -= 1\n",
    "                if indeg_col[j] == 0:\n",
    "                    q2.append(j)\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        for i, x in enumerate(a1):\n",
    "            for j, y in enumerate(a2):\n",
    "               if x == y:\n",
    "                   ans[i][j] = x \n",
    "        return ans if len(a1) == len(a2) == k else []\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def getArray(cd):\n",
    "            g = defaultdict(list)\n",
    "            d = [0] * (k + 1)\n",
    "            s = set((u, v) for u, v in cd)\n",
    "            for u, v in s: \n",
    "                g[u].append(v)\n",
    "                d[v] += 1\n",
    "            rows = [0] * k\n",
    "            idx = 0\n",
    "            q = deque()\n",
    "            for i, x in enumerate(d):\n",
    "                if x == 0 and i:\n",
    "                    q.append(i)\n",
    "            while q:\n",
    "                u = q.popleft()    \n",
    "                rows[idx] = u\n",
    "                idx += 1\n",
    "                for y in g[u]:\n",
    "                    d[y] -= 1\n",
    "                    if d[y] == 0:\n",
    "                        q.append(y)\n",
    "            if idx != k: return []\n",
    "            return rows\n",
    "        rows, cols = getArray(rowConditions), getArray(colConditions)\n",
    "        # 3 1 2,\n",
    "        # 3 2 1\n",
    "        if not rows or not cols: return []\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        mp = {}\n",
    "        for i, x in enumerate(cols):\n",
    "            mp[x] = i\n",
    "        for i, x in enumerate(rows):\n",
    "            r = i\n",
    "            c = mp[x]\n",
    "            ans[r][c] = x\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "    \n",
    "            \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from graphlib import TopologicalSorter, CycleError\r\n",
    "class Solution:\r\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\r\n",
    "        graph: dict[int, set[int]] = {i: set() for i in range(1, k + 1)}\r\n",
    "        for a, b in rowConditions:\r\n",
    "            graph[b].add(a)\r\n",
    "        \r\n",
    "        try:\r\n",
    "            row_seq = {num: i for i, num in enumerate(TopologicalSorter(graph).static_order())}\r\n",
    "        except CycleError:\r\n",
    "            return list()\r\n",
    "        \r\n",
    "        for g in graph.values():\r\n",
    "            g.clear()\r\n",
    "\r\n",
    "        for l, r in colConditions:\r\n",
    "            graph[r].add(l)\r\n",
    "        \r\n",
    "        res = [[0] * k for _ in range(k)]\r\n",
    "        try:\r\n",
    "            for i, num in enumerate(TopologicalSorter(graph).static_order()):\r\n",
    "                res[row_seq[num]][i] = num\r\n",
    "        except CycleError:\r\n",
    "            return list()\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def go(conditions):\n",
    "            deg = [0] * (k + 1)\n",
    "            g = [[0] * (k + 1) for _ in range(k + 1)]\n",
    "            seq = [0] * (k + 1)\n",
    "            for a, b in conditions:\n",
    "                deg[b] += 1\n",
    "                g[a].append(b)\n",
    "            q = []\n",
    "            now = 0\n",
    "            for i in range(1, k + 1):\n",
    "                if deg[i] == 0:\n",
    "                    q.append(i)\n",
    "                    seq[i] = now\n",
    "                    now += 1\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for node in tmp:\n",
    "                    for son in g[node]:\n",
    "                        deg[son] -= 1\n",
    "                        if deg[son] == 0:\n",
    "                            q.append(son)\n",
    "                            seq[son] = now\n",
    "                            now += 1\n",
    "            if now != k:\n",
    "                return []\n",
    "            return seq\n",
    "        \n",
    "        row = go(rowConditions)\n",
    "        if not row:\n",
    "            return []\n",
    "        col = go(colConditions)\n",
    "        if not col:\n",
    "            return []\n",
    "        ret = [[0] * k for _ in range(k)]\n",
    "        for i in range(1, k + 1):\n",
    "            ret[row[i]][col[i]] = i\n",
    "        return ret\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def topo_sort(s: List):\n",
    "            g = [[] * (k + 1) for _ in range(k + 1)]\n",
    "            ind = [0] * k\n",
    "            for a, b in s:\n",
    "                g[a].append(b)\n",
    "                ind[b - 1] += 1\n",
    "            order = []\n",
    "            q = deque([i + 1 for i, x in enumerate(ind) if x == 0])\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                order.append(x - 1)\n",
    "                for y in g[x]:\n",
    "                    ind[y - 1] -= 1\n",
    "                    if ind[y - 1] == 0:\n",
    "                        q.append(y)\n",
    "            return order if len(order) == k else None\n",
    "\n",
    "        rows = topo_sort(list(map(list, set(map(tuple, rowConditions)))))\n",
    "        if not rows: return []\n",
    "        cols = topo_sort(list(map(list, set(map(tuple, colConditions)))))\n",
    "        if not cols: return []\n",
    "\n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        pos = {x:i for i, x in enumerate(cols)}\n",
    "\n",
    "        for i, x in enumerate(rows):\n",
    "            ans[i][pos[x]] = x + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        def go(conditions):\n",
    "            deg = [0] * (k + 1)\n",
    "            g = [[0] * (k + 1) for _ in range(k + 1)]\n",
    "            seq = [0] * (k + 1)\n",
    "            for a, b in conditions:\n",
    "                deg[b] += 1\n",
    "                g[a].append(b)\n",
    "            q = []\n",
    "            now = 0\n",
    "            for i in range(1, k + 1):\n",
    "                if deg[i] == 0:\n",
    "                    q.append(i)\n",
    "                    seq[i] = now\n",
    "                    now += 1\n",
    "            while q:\n",
    "                node = q.pop()\n",
    "                for son in g[node]:\n",
    "                    deg[son] -= 1\n",
    "                    if deg[son] == 0:\n",
    "                        q.append(son)\n",
    "                        seq[son] = now\n",
    "                        now += 1\n",
    "            return [] if now != k else seq\n",
    "        \n",
    "        row = go(rowConditions)\n",
    "        if not row:\n",
    "            return []\n",
    "        col = go(colConditions)\n",
    "        if not col:\n",
    "            return []\n",
    "        ret = [[0] * k for _ in range(k)]\n",
    "        for i in range(1, k + 1):\n",
    "            ret[row[i]][col[i]] = i\n",
    "        return ret\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def toposort(n: int, edges: List[List[int]]) -> List[int]:\n",
    "    '''\n",
    "    n: 共有 n 个节点, 节点编号从 0 到 n - 1\n",
    "    edges: 形如 [[x1, y1], [x2, y2], ...], 表示节点 x 到 节点 y 有一条有向边, 目标是 x 要排在 y 之前\n",
    "    '''\n",
    "    indegree = [0] * n\n",
    "    g = [[] for _ in range(n)]\n",
    "    for x, y in edges:\n",
    "        g[x].append(y)\n",
    "        indegree[y] += 1\n",
    "\n",
    "    q = deque([i for i, v in enumerate(indegree) if v == 0])\n",
    "    ans = []\n",
    "\n",
    "    while q:\n",
    "        node = q.popleft()\n",
    "        ans.append(node)\n",
    "\n",
    "        for ch in g[node]:\n",
    "            indegree[ch] -= 1\n",
    "            if indegree[ch] == 0:\n",
    "                q.append(ch)\n",
    "\n",
    "    return ans if len(ans) == n else []\n",
    "\n",
    "class Solution:\n",
    "    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n",
    "        m, n  = len(colConditions), len(rowConditions)\n",
    "        row, col = [], []\n",
    "        for a, b in rowConditions:\n",
    "            row.append([a - 1, b - 1])\n",
    "        for a, b in colConditions:\n",
    "            col.append([a - 1, b - 1])\n",
    "        res1 = toposort(k, row)\n",
    "        res2 = toposort(k, col)\n",
    "        if not res1 or not res2:\n",
    "            return []\n",
    "        \n",
    "        ans = [[0] * k for _ in range(k)]\n",
    "        dic1, dic2 = {}, {}\n",
    "        for i, x in enumerate(res1):\n",
    "            dic1[x + 1] = i\n",
    "        for i, x in enumerate(res2):\n",
    "            dic2[x + 1] = i\n",
    "        \n",
    "        for i in range(1, k + 1):\n",
    "            ans[dic1[i]][dic2[i]] = i\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
